package com.adee.algorithm.structure;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import java.util.function.Consumer;

/**
 * 二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），也称二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
 *
 * （1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
 * （2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
 * （3）左、右子树也分别为二叉排序树；
 *
 */
public class Test005_BinaryTree {
    public static void main(String[] args) {

    }
}

// E 节点类型， V 节点中数据类型
interface BinaryTree<E> {
    /*
    * 增删改查
    * */
    // 插入元素
    boolean add(E e);
    // 删除指定位置的元素
    default boolean remove(E el) {
        throw new UnsupportedOperationException("不支持删除元素");
    }
    // 获取指定位置的元素
    boolean exist(E el);
    // 更新指定位置的元素的值
    E update(E el);

    /*
    * 遍历
    * */
    // 前序遍历，又名 深度优先遍历
    void forEachPre(Consumer<E> c);
    // 中序遍历
    void forEachMid(Consumer<E> c);
    // 后序遍历
    void forEachPost(Consumer<E> c);
    // 广度优先查找，BFS（breadth first search），又名宽度优先查找，一层一层遍历
    void forEachLevelOrder(Consumer<E> c);

    /*
    * 排序
    * */
    // 升序排序，根节点最小
    void orderAscend();
    // 降序排序，根节点最大
    void orderDescend();

    /*
    * 其他
    * */
    // 获取根节点
    E getRoot();

}

class ArrayBinaryTree<E> implements BinaryTree<E> {
    private static int INIT_CAPACITY = 16;
    private TreeNode<E>[] arr = (TreeNode<E>[]) new Object[INIT_CAPACITY];
    private int size = 0;
    private int capacity = INIT_CAPACITY;
    private float loadFactor = 0.75f;

    // 扩容
    private void expandCapacity() {
        if(capacity < (Integer.MAX_VALUE>>1))
            capacity = capacity << 1;
        else if(capacity == (Integer.MAX_VALUE - 1))
            throw new IllegalStateException("容量超出Integer.MAX_VALUE - 1");
        else
            capacity = Integer.MAX_VALUE - 1;

        TreeNode<E>[] newArr = (TreeNode<E>[]) new Object[capacity];
        System.arraycopy(arr, 0, newArr, 0, size);
        arr = newArr;
    }

    // 判断是否需要扩容
    private void ensureCapacity() {
        if(size >= capacity*loadFactor) {
            expandCapacity();
        }
    }

    @Override
    public boolean add(E e) {
        cannotNull(e);
        ensureCapacity();
        arr[size++] = new TreeNode<>(e);
        return true;
    }

    @Override
    public boolean remove(E el) {
        return false;
    }

    @Override
    public boolean exist(E el) {

        return false;
    }

    @Override
    public E update(E el) {
        return null;
    }

    // 前序遍历
    @Override
    public void forEachPre(Consumer<E> c) {
        // 前序遍历，根节点->左子树->右子树 ，又名 深度优先遍历
        Stack<TreeNode<E>> stack = new Stack<>();
        stack.push(rootNode());
        while (!stack.isEmpty()) {
            TreeNode<E> n = stack.pop();
            c.accept(n.value);
            if(n.rightChild != null) stack.push(n.rightChild);
            if(n.leftChild != null) stack.push(n.leftChild);
        }
    }

    // 中序遍历
    @Override
    public void forEachMid(Consumer<E> c) {
        // 中序遍历，左子树->根节点->右子树
        Stack<TreeNode<E>> stack = new Stack<>();
        TreeNode<E> node = rootNode();
        while(node != null || !stack.isEmpty()) {
            if(node != null) {
                stack.push(node);
                node = node.leftChild;
            } else {
                TreeNode<E> pop = stack.pop();
                c.accept(pop.value);
                node = pop.rightChild;
            }
        }
    }

    // 后序遍历
    @Override
    public void forEachPost(Consumer<E> c) {
        // 后序遍历，左子树->右子树->根节点
        forEachPost1(c);
    }

    @Override
    public void forEachLevelOrder(Consumer<E> c) {
        // 广度优先查找
        TreeNode<E> root = rootNode();
        if (root == null) return;
        LinkedList<TreeNode<E>> list = new LinkedList<>(); // 链表，作为队列
        list.add(root); // 把根节点加入队列尾部
        while (!list.isEmpty()) {
            TreeNode<E> poll = list.poll(); // 从队列头部移除元素
            c.accept(poll.value);
            if(poll.leftChild != null) {
                list.add(poll.leftChild);
            }
            if(poll.rightChild != null) {
                list.add(poll.rightChild);
            }
        }
    }

    // 广度优先遍历的另一种实现，通过尾递归，将结果按层存入二维数组中
    private List<List<E>> forEachLevelOrderWithLevels(Consumer<E> c) {
        List<List<E>> list = new ArrayList<>();
        TreeNode<E> root = rootNode();
        putNodeInLevel(root, 0, list);
        return list;
    }

    // 将node放入第level层，level从0开始
    private void putNodeInLevel(TreeNode<E> node, int level, List<List<E>> list) {
        if(level >= list.size()) { // list.size()表示实际层数
            // 层数不够
            List<E> subList = new ArrayList<>();
            list.add(subList);
             subList.add(node.value);
        }else {
            list.get(level).add(node.value);
        }
        putNodeInLevel(node.leftChild, level+1, list);
        putNodeInLevel(node.rightChild, level+1, list);
    }


    /**
     * 第一种实现方法，使用两个栈
     *
     * 用非递归方式遍历二叉树，需要引入额外的数据结构栈(stack),其基本流程如下：
     * 1、申请两个栈stack，然后将头节点压入指定stack中。
     * 2、从stack中弹出栈顶节点，放入另外一个栈中
     * 3、将其左孩子节点（不为空的话）先压入stack中
     * 4、将其右孩子节点（不为空的话）压入stack中。
     * 5、不断重复步骤2、3、4，直到stack为空。
     * 6、重复访问另外一个栈，直至栈空
     *
     */
    private void forEachPost1(Consumer<E> c) {
        Stack<TreeNode<E>> s1 = new Stack<>();
        Stack<TreeNode<E>> s2 = new Stack<>();
        s1.push(rootNode());
        while (!s1.isEmpty()) {
            TreeNode<E> pop = s1.pop();
            s2.push(pop);
            if(pop.leftChild != null) {
                s1.push(pop.leftChild);
            }
            if(pop.rightChild != null) {
                s1.push(pop.rightChild);
            }
        }
        while (!s2.isEmpty()) {
            c.accept(s2.pop().value);
        }
    }

    // 第二种实现方法，使用一个栈
    private void forEachPost2(Consumer<E> consumer) {
        Stack<TreeNode<E>> stack = new Stack<>();
        TreeNode<E> tree = rootNode();
        stack.push(tree);
        TreeNode<E> c;
        while (!stack.isEmpty()) {
            c = stack.peek();
            if(c.leftChild != null && tree != c.leftChild && tree != c.rightChild) {
                stack.push(c.leftChild);
            }else if(c.rightChild != null && c.rightChild != tree) {
                stack.push(c.rightChild);
            }else {
                consumer.accept(stack.pop().value);
                tree = c;
            }
        }
    }

    @Override
    public void orderAscend() {

    }

    @Override
    public void orderDescend() {

    }

    @Override
    public E getRoot() {
        return size > 0 ? arr[0].value : null;
    }

    private TreeNode<E> rootNode() {
        return size > 0 ? arr[0] : null;
    }

    private void cannotNull(Object obj) {
        if (obj == null) throw new NullPointerException();
    }

    private static class TreeNode<V> {
        private V value;
        private TreeNode<V> leftChild;
        private TreeNode<V> rightChild;

        public TreeNode(V v) {
            this.value = v;
        }
    }
}

abstract class LinkedBinaryTree<E> implements BinaryTree<E> {


}

